package master;

/**
 *
 * 跳跃游戏2
 *
 * @author chenyw
 * @date 2022/7/25 14:49
 */
public class M45jump {
    public static void main(String[] args) {
        int jump = new M45jump().jump(new int[]{2, 3, 1, 1, 4});
    }

/*    //动归
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] + j >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
//        for (int i : dp) {
//            System.out.println(i);
//        }
        return dp[n - 1];*/

    //贪心
    public int jump(int[] nums) {
        int n = nums.length;
        int preMax = 0;
        int maxPosition = 0;
        int steps = 0;
        //不用走到走后一步
        for (int i = 0; i < n - 1; i++) {
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == preMax) {
                preMax = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
